﻿#define _CRT_SECURE_NO_WARNINGS 1
// 原题连接：https://www.acwing.com/problem/content/207/
/*
题目描述：
在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)
。

给定整数 n
，求 Fibnmod10000
。

输入格式
输入包含不超过 100
 组测试用例。

每个测试用例占一行，包含一个整数 n
。

当输入用例 n=−1
 时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围
0≤n≤2×109
输入样例：
0
9
999999999
1000000000
-1
输出样例：
0
34
626
6875
*/

// 开始解题：
// 方法——矩阵快速幂
#include <iostream>
#include <vector>
using namespace std;
const int mod = 10000;

// 两个矩阵相乘
vector<vector<int>> mul(const vector<vector<int>>& grid1, const vector<vector<int>>& grid2) {
    int n = grid1.size();
    int m = grid2[0].size();
    int K = grid1[0].size();
    vector<vector<int>> ret(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < K; k++) {
                ret[i][j] = (ret[i][j] + (long long)grid1[i][k] * grid2[k][j]) % mod;
            }
        }
    }
    return ret;
}

// 矩阵快速幂
vector<vector<int>> qmi(vector<vector<int>>& base, long long p) {
    int n = base.size();
    vector<vector<int>> ret(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        ret[i][i] = 1;
    }
    while (p) {
        if (p & 1) {
            ret = mul(ret, base);
        }
        base = mul(base, base);
        p >>= 1;
    }
    return ret;
}



int main() {
    long long n = 0;

    while (true) {
        scanf("%lld", &n);
        if (-1 == n) {
            break;
        }
        if (0 == n) {
            printf("0\n");
            continue;
        }
        if (1 == n) {
            printf("1\n");
            continue;
        }
        vector<vector<int>> start = { { 1, 0 } };
        vector<vector<int>> base = { { 1, 1 }, { 1, 0 } };
        vector<vector<int>> ret = mul(start, qmi(base, n - 1));
        printf("%d\n", ret[0][0]);

    }
    return 0;
}